package 不同路径II;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/4/29 12:28
 * @description:
 */
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // ① dp数组以及含义：dp[i][j]表示达到坐标（i，j）最多有多少种路径
        // ② 状态转移公式：dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        //                  如果当前网格是障碍物，那么就令dp[i][j] = 0;表示不可达
        // ③ dp数组初始化：需要初始化第一行和第一列的元素，可达就初始化为1，不可达就初始化为0
        // ④ 遍历顺序：从左到右，从上到下
        // ⑤ 举例推到dp数组：如果 obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
        //             dp:      0    1   2
        //                 0    1    1   1
        //                 1    1    0   1
        //                 2    1    1   2

        int rowLen = obstacleGrid.length;
        int colLen = obstacleGrid[0].length;
        int[][] dp = new int[rowLen][colLen];
        // init dp
            dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 1; i < rowLen; i++) {
            // row
            dp[i][0] = (obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0) ? 0 : 1;
        }
        for (int i = 1; i < colLen; i++) {
            // column
            dp[0][i] = (obstacleGrid[0][i] == 1 || dp[0][i - 1] == 0) ? 0 : 1;
        }
//        printDP(dp);

        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
//                printDP(dp);
            }
        }

        return dp[rowLen-1][colLen-1];
    }


    private void printDP(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("---------------------");
    }
}
